package algorithm.middle;

public class MaximumSwap670 {
    public static int maximumSwap(int num) {
        String number = num + "";
        char[] array = number.toCharArray();
        for (int i = 0; i < array.length; i++) {
            if (array[i] == '9') {
                continue;
            }
            char curMax = array[i];
            int index = -1;
            for (int j = array.length - 1; j > i; j--) {
                if (array[j] == '9') {
                    array[j] = array[i];
                    array[i] = '9';
                    return Integer.parseInt(new String(array));
                }
                if (array[j] > curMax) {
                    curMax = array[j];
                    index = j;
                }
            }
            if (index != -1) {
                char temp = array[i];
                array[i] = array[index];
                array[index] = temp;
                return Integer.parseInt(new String(array));
            }
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println(maximumSwap(9892135));
    }

    /**
     *  https://leetcode.cn/problems/maximum-swap/solution/by-muse-77-hwnt/
     * @param num
     * @return
     */
    public int maximumSwap2(int num) {
        char[] numArr = String.valueOf(num).toCharArray();
        int[] maxIndexs = new int[numArr.length];

        int index = numArr.length - 1;
        for (int i = numArr.length - 1; i >= 0; i--) {
            if (numArr[i] > numArr[index]) index = i;
            maxIndexs[i] = index;
        }

        for (int i = 0; i < numArr.length; i++) {
            if (numArr[i] != numArr[maxIndexs[i]]) {
                char temp = numArr[i];
                numArr[i] = numArr[maxIndexs[i]];
                numArr[maxIndexs[i]] = temp;
                break;
            }
        }

        return Integer.valueOf(new String(numArr));

    }


}
